package org.skywork.top.core.algorithm.tree;

import org.skywork.top.core.algorithm.support.TreeNode;

/**
 * 平衡二叉树
 */
public class no_110 {

    /**
     * 给定一个二叉树，判断它是否是 平衡二叉树
     */
    public boolean isBalanced(TreeNode root) {

        /**
         * 示例 1：
         * 输入：root = [3,9,20,null,null,15,7]
         * 输出：true
         *
         *
         * 示例 2：
         * 输入：root = [1,2,2,3,3,null,null,4,4]
         * 输出：false
         *
         *
         * 示例 3：
         * 输入：root = []
         * 输出：true
         *
         */

        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if (left == -1) return -1;
        int right = recur(root.right);
        if (right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }


    public int depth(TreeNode node, int num){
        int left = num;
        if(node.left != null){
            left++;
            left = depth(node.left, left);
        }
        int right = num;
        if(node.right != null){
            right++;
            right = depth(node.right, right);
        }
        return Math.max(left, right);
    }
}
